package com.zh.note.huawei.onehundred.乘坐保密电梯;

import java.util.*;

/**
 * @Author: zhanghuan
 * @date: 2023/8/21 18:58
 * @description: create it
 */
public class Main {
    // 记录下 <= 目标楼层并且是最高的那个楼层
    static int min = Integer.MAX_VALUE;
    // 结果
    static List<Integer> res;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // String s1 = scanner.nextLine();
        // String s2 = scanner.nextLine();
        String s1 = "7 3";
        String s2 = "1 2 6";
        String[] split = s1.split(" ");

        int target = Integer.parseInt(split[0]);
        int n = Integer.parseInt(split[1]);
        Integer[] nums = new Integer[n];

        split = s2.split(" ");

        // 输入处理
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }

        // 输出结果要求先处理大值，所以排序
        Arrays.sort(nums, Comparator.reverseOrder());
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[n];
        dfs(nums, 1, 0, 0, target, path, used);

        if (!res.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            sb.append(res.get(0));
            for (int i = 1; i < res.size(); i++) {
                sb.append(" ").append(res.get(i));
            }
            System.out.println(sb.toString());
        } else {
            System.out.println(-1);
        }
    }

    /**
     * 全排列的变形
     * @param nums    数组序列
     * @param diction 记录本次上还是下
     * @param level   目前所在楼层
     * @param index   第几次楼层移动
     * @param target  目标楼层
     * @param path    在楼层上下过程中的记录
     * @param used    记录哪些移动楼层数字已经被使用
     */
    private static void dfs(Integer[] nums, int diction, int level, int index, int target, List<Integer> path, boolean[] used) {
        // 如果使用完所有数字
        if (index == nums.length) {
            System.out.println(path);
            // 能够达到楼层或者小于该楼层最近的序列，那就是找出小于等于目标楼层最高的那一层
            if (target - level >= 0 && target - level < min) {

                min = target - level;
                res = new ArrayList<>(path);
            }
            return;
        }

        // 遍历序列，下一步的可选项一一枚举尝试
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            // 根据方向来决定是上还是下
            if (diction == 1) {
                dfs(nums, 0, level + nums[i], index + 1, target, path, used);
            } else {
                dfs(nums, 1, level - nums[i], index + 1, target, path, used);
            }
            // 回溯
            path.remove(path.size() - 1);
            used[i] = false;

        }
    }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// public class Main {
//     // 最小差值
//     static int minDiffer = Integer.MAX_VALUE;
//
//     public static void main(String[] args) {
//         Scanner sc = new Scanner(System.in);
//         // int target = sc.nextInt();
//         // int count = sc.nextInt();
//         // String input2 = sc.nextLine();
//         int target = 5;
//         int count = 3;
//         String input2 = "1 2 6";
//         List<Integer> nums = Arrays.stream(input2.split(" ")).map(Integer::parseInt).collect(Collectors.toList());
//         int sum = nums.stream().mapToInt(Integer::valueOf).sum();
//
//         int requiredUpCount = count / 2 + count % 2;
//         int requiredSum = (sum + target) / 2;
//         // int requiredSum = 9;
//         //降序排列
//         Collections.sort(nums, Comparator.reverseOrder());
//         Deque<Integer> path = new LinkedList<>();
//         List<List<Integer>> res = new ArrayList<>();
//         dfs(nums, 0, path, 0, requiredSum, requiredUpCount, res);
//
//         List<Integer> up = new ArrayList<>();
//         List<Integer> down = new ArrayList<>();
//         // 因为nums已经是降序排列了，所以这里的两个list添加后也是降序排列
//         List<Integer> list = res.get(0);
//         for (int i = 0; i < nums.size(); i++) {
//             if (res.get(0).contains(nums.get(i))) {
//                 up.add(nums.get(i));
//             } else {
//                 down.add(nums.get(i));
//             }
//         }
//
//         List<Integer> temp = new ArrayList<>();
//         for (int i = 0; i < nums.size() / 2; i++) {
//             temp.add(up.get(0));
//             up.remove(0);
//             temp.add(down.get(0));
//             down.remove(0);
//         }
//
//         if (!up.isEmpty()) {
//             temp.add(up.get(0));
//             up.remove(0);
//         }
//
//         System.out.println(temp);
//
//
//     }
//
//     //组合问题，选k个数组合,和最接近target
//     private static void dfs(List<Integer> nums, int startIndex, Deque<Integer> path, int sum, int target, int k, List<List<Integer>> res) {
//         if (k == path.size()) {
//             if (sum < target) {
//                 return;
//             }
//             int temp = sum - target;
//             if (temp < minDiffer) {
//                 res.clear();
//                 minDiffer = temp;
//                 res.add(new ArrayList<>(path));
//                 return;
//             }
//         }
//
//         for (int i = startIndex; i < nums.size(); i++) {
//             int num = nums.get(i);
//             sum += num;
//             path.add(num);
//             dfs(nums, i + 1, path, sum, target, k, res);
//             path.removeLast();
//             sum -= num;
//
//         }
//     }
// }
